![]()
https://www.acmicpc.net/problem/15808알고리즘 분류그래프 이론데이크스트문제영선이는 요즘 여행에 빠져있다. 그래서 짧게나마 여행을 다녀오고 싶었던 영선이는 주말을 활용해 여행 갈 계획을 세우고 있다. 하지만 영선이는 가고 싶은 여행지가 너무 많아 고민 중이며, 숙소 또한 좋은 곳으로 가고 싶기에 여행지와 숙소를 기반으로 계획을 작성하려 한다.영선이는 가고 싶은 여행지 리스트와 숙소 리스트를 미리 조사하여 작성했다. 그리고 각 여행지와 숙소에 조사한 자료를 통해 기대치를 매겼다. 시간이 없기에 영선이는 여행지 한 곳, 숙소 한 곳을 방문할 것이며, 이때 선택된 장소들의 기대치 합이 최대가 되는 여행 계획을 작성할 것이다.또한, 여행지와 숙소 사이의 거리가 멀다면 여행지에서 관광을..
최소비용 구하기 2 스페셜 저지!https://d2gd6pc034wcta.cloudfront.net/tier/13.svg시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB3361912739908636.652%문제n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.입력첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리..
![]()
문제 링크https://www.acmicpc.net/problem/1719접근 방법다익스트라 알고리즘은 "어떤 노드까지의 최단거리를 알 때, 그 노드와 연결된 노드들의 최단 거리를 갱신"하며 정답을 구하는 알고리즘이다.그러한 알고리즘의 특징을 이용해서 다음과 같은 접근을 하였다.다익스트라 알고리즘을 진행할 때, 알고리즘의 효율성을 위해 우선순위 큐를 사용한다. 우선순위 큐에는 최단 거리가 갱신된 노드가 담긴다.우선순위 큐에서 어떤 노드 A가 나온다고 가정해보자. (우선순위 큐의 top이 노드 A)노드 A로 향하는 최단 거리는 확정되었다. (큐의 내용과 실제 노드 A의 최단 거리를 비교해야함)A 노드가 다익스트라 알고리즘을 실행한 루트 노드가 아니라면 루트 노드에서 A 노드로 향하는 이전 노드가 있을 것이..
https://www.acmicpc.net/problem/2606 코드from collections import dequen=int(input()) # 컴퓨터 개수v=int(input()) # 연결선 개수graph = [[] for i in range(n+1)] # 그래프 초기화visited=[0]*(n+1) # 방문한 컴퓨터인지 표시for i in range(v): # 그래프 생성 a,b=map(int,input().split()) graph[a]+=[b] graph[b]+=[a]visited[1]=1 Q=deque([1])while Q: c=Q.popleft() for nx in graph[c]: if visited[nx]==0: Q.a..
문제 링크https://www.acmicpc.net/problem/1327접근 방법처음 문제를 읽었을 때 반드시 K 개수의 숫자를 뒤집어야함에 유의하지 않고 생각해서 K = 3이고 초기 순열이 5 4 3 2 1인 경우 숫자 1, 2는 뒤집지 못한다는 점을 놓쳐서 시간을 많이 허비했습니다. 역시 문제는 꼼꼼히 읽어야합니다.해당 문제에서 만들 수 있는 순열을 순열이 아닌 모든 숫자를 이어붙인 하나의 숫자(또는 문자열)라고 생각해보겠습니다.예를들어 5 4 1 2 3이라는 순열이 주어졌을 때 이를 순열로 보는 것이 아닌, 54123이라는 숫자(또는 문자열)로 생각한다면1 ~ N까지의 숫자가 하나씩 존재하고 N이 8로 매우 작기 때문에 러프하게 생각해 봤을때 어떤 순열이 주어져도 주어진 순열에서 만들 수 있는 순..
https://www.acmicpc.net/problem/14490문제n, m이 :을 사이에 두고 주어질 때 두 수를 최대한으로 약분해서 출력한다. (1 풀이두 수의 최대 공약수 x를 구하여 n/x : m/x를 출력한다. 코드#include #include #include using namespace std;string s;int n, m, x = 1;vector v;//최대공약수로 나누기int main() { cin >> s; for (int i = 0; i
![]()
https://www.acmicpc.net/problem/15874문제 분석분류문자열구현문제 설명여러분들은 고대 로마의 정치인 율리우스 카이사르를 알고 있는가? 그는 정말 대단한 사람이다! 그는 로마의 독재자로도 유명하지만, 고대 암호의 대표격이라 할 수 있는 카이사르 암호(Caesar Cipher)를 만든 사람이기도 하다.카이사르 암호는 다음과 같은 방식으로 이뤄진다.알파벳으로 평문을 작성한다.해당 평문을 얼마나 밀지를 결정한다. 민다는 것은, 한 글자를 알파벳 상의 다음 글자로 바꾸는 것을 말한다. 예를 들어 네 번 밀기로 결정했다면, A는 E로, V는 Z로 바뀐다. 만약 Z를 한 번 더 민다면 A가 된다. 이를 표로 나타내면 다음과 같다.원문ABCDE...VWXYZ암호문EFGHI...ZABCD평문의..
https://www.acmicpc.net/problem/5430 문제선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의..
문제https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 코드import java.util.*;class Solution { static boolean isFound = false; public String[] solution(String[][] ticketInfos) { String[] answer = new String[ticketInfos.length + 1]; Arrays.sort(ticketInfos, (s1..
![]()
문제 설명네트워크로 연결되어있는 컴퓨터들이 있는데 1번 컴퓨터가 바이러스에 걸리면 1번 컴퓨터와 연결된 컴퓨터는 모두 바이러스에 감염된다.이때 1번 컴퓨터로 인해 바이러스에 감염된 컴퓨터의 개수를 구하라입력컴퓨터 대수연결된 컴퓨터쌍 수컴퓨터 쌍 1컴퓨터 쌍 2컴퓨터 쌍 3.....ex)761 22 31 55 25 64 7출력감염된 컴퓨터 개수코드(입력 받는 부분은 따로 첨부하지 않았다)이 문제는 항상 1번 컴퓨터에서 바이러스가 시작되는 것으로 정해져있으므로 함수를 만들지 않고 바로 실행하는 코드로 만들었다먼저 visit 리스트를 만들어주고 방문한 노드를 저장할 queue도 만들어준다(14, 15번 줄)그리고 while 문을 이용하여 queue에 더이상 방문할 노드가 없을 때까지 반복한다.한번 방문을 할때..
https://www.acmicpc.net/problem/15723코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;vector graph[27];int bfs(int start,int find){ bool visited[27] = { false, }; queue q; q.push(start); visited[start] = true; int ans = 0; // 큐가 빌 때까지 반복 while (!q.empty()) { // 큐에서 하나의 원소를 뽑아 출력 int x = q.front(..
https://www.acmicpc.net/problem/10798문제아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다. 이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다. A A B C D Da f z z 0 9 1 2 1a 8 E W g 6P 5 h 3 k x한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 ..
